package com.tarry.linkedlist;

import java.util.Objects;

/**
 *  链表的实现
 * @param <E>
 */
public class LinkedList<E> {
    public class Node<E> {
        public E element;
        public LinkedList<E>.Node<E> next;
    }

    private Node<E> head = null;

    public Node<E> find(E item){
        Node<E> tmp = this.head;

        //TODO 存疑当为对象时，使用equals比较是否正确
        while ( !Objects.isNull(tmp) && !Objects.equals(tmp.element,item)){
            tmp = tmp.next;
        }
        return tmp;
    }

    /**
     *
     * @param preNode 前驱节点
     * @param newNode 新增节点
     * @return
     */
    public boolean add(Node<E> preNode,Node<E> newNode){
        if (Objects.isNull(preNode)) {
            newNode.next = head;
            head = newNode;
        }else {
            newNode.next = preNode.next;
            preNode.next = newNode;
        }
        return true;
    }

    /**
     *
     * @param preNode 前驱节点
     * @param delNode 需要删除的节点
     * @return
     */
    public boolean remove(Node<E> preNode,Node<E> delNode){
        // 删除当delNode为头节点
        if (Objects.isNull(preNode)) {
            head = head.next;
        }else {
            preNode.next = delNode.next;
        }
        return true;
    }

    /**
     *  根据下标查找元素：
     *  <br>
     *  <p>
     *      在java中LinkedList使用size计数在add和remove时进行更新，
     *      当根据下标查找时，通过size和index进行比较使用二分法进行查找
     *  </p>
     * @param index
     * @return
     */
    public E get(int index){
        Node<E> p = head;
        int loopNum = 0;
        while ( !Objects.isNull(p) && loopNum != index){
            p = head.next;
            loopNum ++ ;
        }
        return (E) p;
    }
}
